/*
 * Copyright (c) 2010, okazoh_tk. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *  - Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 *  - Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *  - Neither the name of the copyright holder nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include "alkes/core/Deque.h"

namespace alkes {

#define INVALID_INDEX   (-1)

Deque::Deque(DequeIteratorFactory* factory)
: count_(0)
, first_(0)
, last_(0)
, factory_(factory)
{
}

Deque::~Deque()
{
    clear();
}

int32_t Deque::count() const
{
    return count_;
}

int32_t Deque::index(void* object) const
{
    if (!object)
        return INVALID_INDEX;

    Iterator iter = getFirst();
    int32_t idx = 0;

    while (iter)
    {
        if (*iter == object)
            break;

        ++idx;
        iter = iter->getNext();
    }

    if (!iter)
        idx = INVALID_INDEX;

    return idx;
}

int32_t Deque::index(Iterator iter) const
{
    if (!iter)
        return INVALID_INDEX;

    int32_t idx = -1;

    do
    {
        ++idx;
        iter = iter->getPrev();

    } while (iter);

    return idx;
}

bool Deque::push(void* object)
{
    if (!object)
        return false;

    DequeIterator* iter = createIterator(object, getLast(), 0);

    if (iter)
    {
        if (getLast())
            getLast()->setNext(iter);
        else
            setFirst(iter);

        setLast(iter);

        ++count_;
    }

    return 0 != iter;
}

bool Deque::unshift(void* object)
{
    if (!object)
        return false;

    DequeIterator* iter = createIterator(object, 0, getFirst());

    if (iter)
    {
        if (getFirst())
            getFirst()->setPrev(iter);
        else
            setLast(iter);

        setFirst(iter);

        ++count_;
    }

    return 0 != iter;
}

bool Deque::insert(int32_t idx, void* object)
{
    if (!object)
        return false;

    // push to tail.
    if (count_ <= idx)
        return push(object);
    else
        return insert(getIterator(idx), object);
}

bool Deque::insert(Iterator iter, void* object)
{
    if (!object || !iter)
        return false;

    DequeIterator* new_iter = createIterator(object, iter->getPrev(), iter);
    if (new_iter)
    {
        iter->setPrev(new_iter);
        if (getFirst() == iter)
            setFirst(new_iter);

        ++count_;
    }

    return 0 != new_iter;
}

void* Deque::pop()
{
    if (!getLast())
        return 0;

    // last
    DequeIterator* iter = getLast();

    if (iter->getPrev())
        iter->getPrev()->setNext(0);
    else
        setFirst(0);

    setLast(iter->getPrev());

    void* object = *iter;

    destroyIterator(iter);

    --count_;

    return object;
}

void* Deque::shift()
{
    if (!getFirst())
        return 0;

    // first
    DequeIterator* iter = getFirst();

    if (iter->getNext())
        iter->getNext()->setPrev(0);
    else
        setLast(0);

    setFirst(iter->getNext());

    void* object = *iter;

    destroyIterator(iter);

    --count_;

    return object;
}

bool Deque::remove(void* object)
{
    return remove(find(object));
}

bool Deque::remove(Iterator iter)
{
    if (!iter)
        return false;

    if (iter->getPrev())
        iter->getPrev()->setNext(iter->getNext());
    else
        setFirst(iter->getNext());

    if (iter->getNext())
        iter->getNext()->setPrev(iter->getPrev());
    else
        setLast(iter->getPrev());

    destroyIterator(iter);

    --count_;

    return true;
}

void Deque::clear()
{
    while (pop())
    {
        ;
    }
}

Deque::Iterator Deque::getLast()
{
    return last_;
}

const Deque::Iterator Deque::getLast() const
{
    return last_;
}

void Deque::setLast(Iterator iter)
{
    last_ = iter;
}

Deque::Iterator Deque::getFirst()
{
    return first_;
}

const Deque::Iterator Deque::getFirst() const
{
    return first_;
}

void Deque::setFirst(Iterator iter)
{
    first_ = iter;
}

Deque::Iterator Deque::iterator(int32_t idx)
{
    return getIterator(idx);
}

const Deque::Iterator Deque::iterator(int32_t idx) const
{
    return getIterator(idx);
}

Deque::Iterator Deque::find(void* object)
{
    return findIterator(object);
}

const Deque::Iterator Deque::find(void* object) const
{
    return findIterator(object);
}

Deque::Iterator Deque::getIterator(int32_t idx) const
{
    if (idx < 0)
        idx = count_ + idx;

    if (count_ <= idx)
        return 0;

    Iterator iter;

    if (idx <= (count_ >> 1))
    {
        iter = getFirst();

        while (0 != idx)
        {
            --idx;
            iter = iter->getNext();
        }
    }
    else
    {
        idx = count_ - idx - 1;

        iter = getLast();

        while (0 != idx)
        {
            --idx;
            iter = iter->getPrev();
        }
    }

    return iter;
}

Deque::Iterator Deque::findIterator(void* object) const
{
    if (!object)
        return 0;

    Iterator iter(getFirst());

    while (iter && object != (*iter))
        iter = iter->getNext();

    return iter;
}

Deque::Iterator Deque::createIterator(void* object, Iterator prev, Iterator next)
{
    return factory_
        ? factory_->construct(object, prev, next)
        : new DequeIterator(object, prev, next);
}

void Deque::destroyIterator(Iterator iter)
{
    if (factory_)
        factory_->destruct(iter);
    else
        delete iter;
}

}
